12.15 Suppose we store, for each node, the number of null links in its subtree; call this the node's weight. Adopt the following strategy: If the left and right subtrees have weights that are not within a factor of 2 of each other, then completely rebuild the subtree rooted at the node. Show the following: a. We can rebuild a node in O(S), where S is the weight of the node. b. The algorithm has amortized cost of O(logN) per insertion. c. We can rebuild a node in a k-d tree in O(S log S) time, where S is the weight of the node. d. We can apply the algorithm to k-d trees, at a cost of O(log2 N) per insertion. - | |
| View Solution | |
| << Back | Next >> |